/**
 * 
 * 项目描述：
 *   给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。
 * 请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，
 * 而不是节点的值的奇偶性。
 */

function ListNode(val, next) {
    this.val = (val === undefined ? 0 : val)
    this.next = (next === undefined ? null : next)
  }
  
  var oddEvenList = function (head) {
    // 链表为空, 直接返回
    if (head === null) {
      return null
    }
    // 链表只有一个节点, 直接返回
    if (head.next === null) {
      return head
    }
    // 第一个为奇数节点, 第二个为偶数节点
    // 奇数节点为 head, 偶数节点为 head.next
    // 奇数节点为 odd, 偶数节点为 even
    // 偶数节点为 evenHead, 用于记录偶数节点
    let odd = head, even = head.next, evenHead = head.next;
    console.log(evenHead)
    
    // 从偶数链表的头节点开始向后遍历
        // 如果当前节点为空，或者后一节点为空，那么说明整个链表已经查看完毕，不需要再遍历了
    while (even !== null && even.next !== null) {

    //   odd.next = even.next;
    //   odd = odd.next;
    //   even.next = even.next.next;
    //   even = even.next;


        // 原先奇数节点的下一个节点是偶数节点，即 even 这个节点
        // 根据数学知识，奇数后面一定是偶数，偶数后面一定是奇数
        // 那么 even.next 节点必然是奇数节点
        // 所以让 odd 这个奇数节点的 next 指针指向 even.next 这个奇数节点
        // 这样，odd 上面都是奇数
        odd.next = even.next;
        // 让 odd 移动到最新的由奇数节点组成的链表的尾部位置
        odd = odd.next;

        // 这个时候，odd.next 必然是偶数节点
        // 所以让 even 这个偶数节点的 next 指针指向 odd.next 这个偶数节点
        even.next = odd.next;
        // 让 even 移动到最新的由偶数节点组成的链表的尾部位置
        even = even.next;
    }
    // odd.next = evenHead;
    // console.log(evenHead, head.next)
    // return head;

    // 此时，原链表所有的节点已经遍历完毕
    // odd 上都是奇数节点
    // even 都是偶数节点
    // 根据题目要求，奇数节点都在偶数节点之前
    // 所以让此时右奇数节点组成的链表的尾部的 next 指针指向由偶数节点组成的链表的头部
    odd.next = evenHead;

    // 最后返回原链表的头部节点就可以了
    // 链表的头部节点没有发生过变化，因为它是奇数节点，并且是第一个奇数节点
    return head;
  };
  
  let node5 = new ListNode(5)
  let node4 = new ListNode(4, node5)
  let node3 = new ListNode(3, node4)
  let node2 = new ListNode(2, node3)
  let node1 = new ListNode(1, node2)
  
  console.log(oddEvenList(node1))